package org.shj.suanfa

import scala.collection.mutable.ListBuffer

/**
 * 在二维空间中的一组气球，给出每个气球的横向直径的起始横坐标和结束横坐标，保证起始横坐标小于结束横坐标
 * 不需要考虑气球的纵坐标，因此横坐标区间可以相互重叠。气球最多有10000个，一支箭可以选定一个横坐标纵向射击
 * 一个气球的横向直径两端横坐标为xbegin, xend,一支箭射击的横坐标为x，如果有xbegin<= x <= xend,则这支箭
 * 可以刺破该气球。没有箭的使用数量限制，并且一支箭可以刺破相应坐标上的所有气球。
 * 求出刺破所有气球所需要的最少的箭的数量
 */
object S002 {
  def main(args: Array[String]): Unit = {
    var arr = ListBuffer((10,16), (1,6), (2,8), (9,12), (7,13))
    
    val b = arr.sortBy[Int](item => item._2)
    var cnt = 1
    var end = b(0)._2
    b.remove(0)
    for(item <- b){
      if(item._1 > end){
        cnt += 1
        end = item._2
      }
    }
    
    println(cnt)
   
    /*var begin = ListBuffer[Int]()
    var end = ListBuffer[Int]()
    arr.foreach(item => {begin += item._1; end += item._2})
    
    //val s = begin.sorted
    val e = end.sorted
    var cnt = 0
    for(i <- e){
      if(arr.length == 0){
        
      }
      for(item <- arr){
        if(item._1 < i){
          arr -= item          
        }
      }
      cnt += 1
      
    }*/
    
  }
}